
//枚举⼦集
//#include <iostream>
//#include <string>
//using namespace std;
//
//int n;
//string path;
//
//void dfs(int level)
//{
//	if (level > n)
//	{
//		cout << path << endl;
//		return;
//	}
//
//	//ѡ N 
//	path += 'N';
//	dfs(level + 1);
//	path.pop_back();
//
//	//Y
//	path += 'Y';
//	dfs(level + 1);
//	path.pop_back();
//}
//
//int main()
//{
//	cin >> n;
//	dfs(1);
//	return 0;
//}
//
// 
// 组合型枚举
//#include <iostream>
//#include <vector>
//using namespace std;
//
//int n, m;
//vector<int> path;
//
//void dfs(int begin)
//{
//	if (path.size() == m)
//	{
//		for (auto ch : path)
//		{
//			cout << ch << " ";
//		}
//		cout << endl;
//		return;
//	}
//
//	for (int i = begin; i <= n; i++)
//	{
//		path.push_back(i);
//		dfs(i + 1);
//		path.pop_back();
//	}
//
//}
//
//int main()
//{
//	cin >> n >> m;
//	dfs(1);
//	return 0;
//}

//枚举排列
//#include <iostream>
//#include <vector>
//#include <unordered_set>
//using namespace std;
//
//int n, k;
//vector<int> path;
//unordered_set<int> mp;
//
//void dfs()
//{
//	if (path.size() == k)
//	{
//		for (auto ch : path)
//		{
//			cout << ch << ' ';
//		}
//		cout << endl;
//		return;
//	}
//
//	for (int i = 1; i <= n; i++)
//	{
//		if (!mp.count(i))
//		{
//			path.push_back(i);
//			mp.insert(i);
//			dfs();
//			path.pop_back();
//			mp.erase(i);
//		}
//	}
//
//}
//
//int main()
//{
//	cin >> n >> k;
//	dfs();
//	return 0;
//}


//全排列问题
//#include <iostream>
//#include <vector>
//using namespace std;
//
//bool st[10] = { 0 };
//int n;
//vector<int> path;
//
//void dfs()
//{
//	if (path.size() == n)
//	{
//		for (auto ch : path)
//		{
//			printf("%5d", ch);
//		}
//		printf("\n");
//		return;
//	}
//
//	for (int i = 1; i <= n; i++)
//	{
//		if (st[i] == 0)
//		{
//			path.push_back(i);
//			st[i] = 1;
//			dfs();
//			path.pop_back();
//			st[i] = 0;
//		}
//	}
//}
//
//int main()
//{
//	cin >> n;
//	dfs();
//	return 0;
//}

// DFS// DFS// DFS// DFS// DFS// DFS// DFS// DFS// DFS


//选数
//#include <iostream>
//using namespace std;
//
//int a[25] = { 0 };
//int n,k;
//int ret = 0;
//int path = 0; // 记录和
//
//bool isprime(int x)
//{
//	if (x == 1)
//		return false;
//	if (x == 2 || x == 3)
//		return true;
//	if (x % 2 == 0 || x % 3 == 0)
//		return false;
//
//	for (int i = 5; i <= x / i; i += 6)
//	{
//		if (x % i == 0 || x % (i + 2) == 0)
//			return false;
//	}
//
//	return true;
//}
//
//void dfs(int pos, int begin)
//{
//	if (pos > k)
//	{
//		if (isprime(path))
//			ret++;
//		return;
//	}
//
//	for (int i = begin; i <= n; i++)
//	{
//		path += a[i];
//		dfs(pos + 1, i + 1);
//		path -= a[i];
//	}
//	
//}
//
//
//int main()
//{
//	cin >> n >> k;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> a[i];
//	}
//
//	dfs(1, 1);
//
//	cout << ret << endl;
//
//	return 0;
//}


//⻜机降落
//#include <iostream>
//#include <algorithm>
//using namespace std;
//
//int t[15] = { 0 };
//int d[15] = { 0 };
//int l[15] = { 0 };
//
//bool st[15] = { 0 };
//
//int T, n;
//
//bool dfs(int pos, int end)
//{
//	if (pos > n)
//	{
//		return true;
//	}
//
//	for (int i = 1; i <= n; i++)
//	{
//		if (st[i])
//			continue;
//		if (end > t[i] + d[i])
//			continue;
//
//		st[i] = 1;
//		int newend = max(end, t[i]) + l[i];
//		if (dfs(pos + 1, newend))
//			return true;
//		st[i] = 0;
//	}
//
//	return false;
//}
//
//
//int main()
//{
//	cin >> T;
//
//	while (T--)
//	{
//		for (int i = 1; i <= 15; i++)
//		{
//			st[i] = 0;
//		}
//		cin >> n;
//		for (int i = 1; i <= n; i++)
//		{
//			cin >> t[i] >> d[i] >> l[i];
//		}
//
//		if (dfs(1,0))
//			cout << "YES" << endl;
//		else
//			cout << "NO" << endl;
//	}
//	return 0;
//}


//
////八皇后//八皇后//八皇后//八皇后
//#include <iostream>
//#include <vector>
//using namespace std;
//
//bool col[15] = { 0 };      //表示列
//bool st1[15 * 2] = { 0 };  //表示主对角线
//bool st2[15 * 2] = { 0 };  //表示副对角线
//
//int n;
//int ret = 0;
//vector<int> path;
//
//void dfs(int x) //一行一行来填写，保证皇后不会因为行打起来，x表示行
//{
//	if (x > n)
//	{
//		ret++;
//		if (ret <= 3)
//		{
//			for (auto ch : path)
//			{
//				cout << ch << " ";
//			}
//			cout << endl;
//		}
//
//		return;
//	}
//
//	for (int y = 1; y <= n; y++)
//	{
//		if (col[y] || st1[y - x + n] || st2[y + x])
//			continue;
//
//		col[y] = st1[y - x + n] = st2[y + x] = true;
//		path.push_back(y);
//		dfs(x + 1);
//		col[y] = st1[y - x + n] = st2[y + x] = false;
//		path.pop_back();
//	}
//}
//
//int main()
//{
//	cin >> n;
//
//	dfs(1);
//
//	cout << ret << endl;
//	return 0;
//}

//数独
//#include <iostream>
//using namespace std;
//
//const int N = 10;
//int n = 9;
//int a[N][N] = { 0 };
//bool row[N][N] = {0};
//bool col[N][N] = {0};
//bool st[N][N][N] = { 0 };
//
//bool dfs(int i, int j) //第i行j列个格子
//{
//	if (j == n)
//	{
//		i++;
//		j = 0;
//	}
//
//	if (i == n)
//		return true;
//
//	if (a[i][j] != 0)
//		return dfs(i, j + 1);
//
//	for (int x = 1; x <= 9; x++)
//	{
//		if (row[i][x] || col[j][x] || st[i / 3][j / 3][x])
//			continue;
//
//		a[i][j] = x;
//		row[i][x] = col[j][x] = st[i / 3][j / 3][x] = true;
//		if (dfs(i, j))
//			return true;
//		row[i][x] = col[j][x] = st[i / 3][j / 3][x] = false;
//		a[i][j] = 0;
//	}
//
//	return false;
//}
//
//int main()
//{
//	for (int i = 0; i < n; i++)
//	{
//		for (int j = 0; j < n; j++)
//		{
//			int x;
//			cin >> x;
//			a[i][j] = x;
//			row[i][x] = col[j][x] = st[i / 3][j / 3][x] = true;
//		}
//	}
//
//	dfs(0, 0);
//
//	for (int i = 0; i < 9; i++)
//	{
//		for (int j = 0; j < 9; j++)
//		{
//			cout << a[i][j] << " ";
//		}
//		cout << endl;
//	}
//
//
//	return 0;
//}




//数的划分
//#include <iostream>
//using namespace std;
//
//int path = 0;
//int ret = 0;
//int n, k;
//
//void dfs(int pos, int begin)
//{
//	if (pos == k)
//	{
//		if (path == n)
//			ret++;
//
//		return;
//	}
//
//	for (int i = begin; i <= n; i++)
//	{
//		if (path + i * (k - pos) > n)
//			return;
//		path += i;
//		dfs(pos + 1, i);
//		path -= i;
//	}
//}
//
//int main()
//{
//	cin >> n >> k;
//	dfs(0, 1);
//
//	cout << ret << endl;
//	return 0;
//}

//小猫爬山
//#include <iostream>
//#include <algorithm>
//using namespace std;
//
//
//int n, m;
//int cnt = 0; // 多少辆车
//int c[20] = { 0 };  //猫猫的重量
//int a[20] = { 0 };  // 每辆车上的重量
//int ret = 20;
//
//bool cmp(int a, int b)
//{
//	return a > b;
//}
//
//void dfs(int x)
//{
//	if (cnt >= ret)
//		return;
//
//	if (x > n)
//	{
//		ret = cnt;
//		return;
//	}
//	
//	//先上已经有的车
//	for (int i = 1; i <= cnt; i++)
//	{
//		if (a[i] + c[x] > m)
//			continue;
//
//		a[i] += c[x];
//		dfs(x + 1);
//		a[i] -= c[x];
//	}
//
//	cnt++;
//	a[cnt] += c[x];
//	dfs(x + 1);
//	a[cnt] = 0;
//	cnt--;
//}
//
//int main()
//{
//	cin >> n >> m;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> c[i];
//	}
//	// 从大往小开始进车，为了最快得到一个结果，进行优化减支
//	sort(c + 1, c + 1 + n, cmp);
//	dfs(1);
//
//	cout << ret << endl;
//	return 0;
//}
//
// 

//记忆化搜索//记忆化搜索//记忆化搜索//记忆化搜索//记忆化搜索//记忆化搜索

//Function
//
//#include <iostream>
//using namespace std;
//
//typedef long long ll;
//
//const int N = 25;
//
//ll a, b, c;
//int f[N][N][N] = { 0 };
//
//ll dfs(ll a, ll b, ll c)
//{
//	
//
//	if (a <= 0 || b <= 0 || c <= 0)
//		return 1;
//
//	if (a > 20 || b > 20 || c > 20)
//		return dfs(20, 20, 20);
//
//	if (f[a][b][c])
//		return f[a][b][c];
//
//	if (a < b && b < c)
//		return f[a][b][c] = dfs(a, b, c - 1) + dfs(a, b - 1, c - 1) - dfs(a, b - 1, c);
//	else
//		return f[a][b][c] = dfs(a - 1, b, c) + dfs(a - 1, b - 1, c) + dfs(a - 1, b, c - 1) - dfs(a - 1, b - 1, c - 1);
//}
//
//int main()
//{
//	while (1)
//	{
//		cin >> a >> b >> c;
//		if (a == b && b == c && a == -1)
//		{
//			break;
//		}
//		printf("w(%lld, %lld, %lld) = %lld\n", a, b, c, dfs(a, b, c));
//	}
//
//	return 0;
//}


// 
//#include <iostream>
//using namespace std;
//
//int t, p;
//
//const int N = 1e4 + 10;
//
//char a[N][N] = { 0 }; // 备忘录
//
//char dfs(int x, int y)
//{
//	//如果备忘录里面有东西就说明之前遇见过，不用重复直接返回
//	if (a[x][y])
//		return a[x][y];
//
//	//这时候说明备忘录里面没有东西，先添加备忘录
//	a[x][y] = '3';
//
//	if (x == 0)
//		return a[x][y] = '1';   //修改备忘录并返回
//	if (y == 0)
//		return a[x][y] = '2';   //修改备忘录并返回
//
//	//修改备忘录并返回
//	return a[x][y] = dfs((x + y) % p, (x + y + y) % p);
//}
//
//int main()
//{
//	cin >> t >> p;
//	while (t--)
//	{
//		int x, y;
//		cin >> x >> y;
//		char ret = dfs(x, y);
//		if (ret == '3')
//			cout << "error" << endl;
//		else
//			cout << ret << endl;
//	}
//	return 0;
//}

//蓝桥杯 迷途之径
//#include <iostream>
//#include <vector>
//using namespace std;
//
//int dx[] = { 0, 0, 1, -1 };
//int dy[] = { -1, 1, 0, 0 };
//
//int n;
//int col[25] = { 0 };
//int row[25] = { 0 };
//bool f[25][25] = { 0 };
//int a[25][25] = { 0 };
//int sum = 0;
//vector<int> ret;
//
//bool dfs(int x, int y)
//{
//
//    if (x == y && x == n && sum == 0)
//    {
//        return true;
//    }
//
//    for (int k = 0; k < 4; k++)
//    {
//        int a = x + dx[k];
//        int b = y + dy[k];
//        if (a < 1 || a > n || b < 1 || b > n)
//            continue;
//
//        if (row[a] - 1 < 0 || col[b] - 1 < 0)
//            continue;
//
//        if (f[a][b])
//            continue;
//
//        f[a][b] = 1;
//        row[a]--;
//        col[b]--;
//        sum -= 2;
//        ret.push_back((a - 1) * n + b - 1);
//        if (dfs(a, b))
//            return true;
//        row[a]++;
//        col[b]++;
//        sum += 2;
//        ret.pop_back();
//        f[a][b] = 0;
//    }
//
//    return false;
//}
//
//int main()
//{
//    
//    cin >> n;
//    if (n == 0)
//    {
//        cout << endl;
//        return 0;
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> col[i];
//        sum += col[i];
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> row[i];
//        sum += row[i];
//    }
//    row[1]--;
//    col[1]--;
//    sum -= 2;
//    ret.push_back(0);
//    dfs(1, 1);
//
//    for (auto ch : ret)
//    {
//        cout << ch << " ";
//    }
//
//    return 0;
//}

//滑雪
//#include <iostream>
//#include <algorithm>
//using namespace std;
//
//int dx[] = { 0, 0, 1, -1 };
//int dy[] = { -1, 1, 0, 0 };
//
//const int N = 110;
//
//int a[N][N] = { 0 };
//int memo[N][N] = { 0 };  //备忘录
//
//int n, m;
//
//int ret = 0;
//
//int dfs(int i, int j)
//{
//
//	int len = 1;
//
//	if (memo[i][j])
//		return memo[i][j];
//
//	
//
//	for (int k = 0; k < 4; k++)
//	{
//		int x = i + dx[k];
//		int y = j + dy[k];
//		
//		if (x < 1 || x > n || y < 1 || y > m)
//			continue;
//		if (a[x][y] >= a[i][j])
//			continue;
//
//		len = max(1 + dfs(x, y), len);
//	}
//
//
//	return memo[i][j] = len;
//}
//
//int main()
//{
//	cin >> n >> m;
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= m; j++)
//		{
//			cin >> a[i][j];
//		}
//	}
//	
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= m; j++)
//		{
//			ret = max(ret, dfs(i, j));
//		}
//	}
//
//	cout << ret << endl;
//
//	return 0;
//}

